Hereafter, a conventional communications system which employs an LDPC code will be explained as an encoding system.
Hereafter, it is assumed that the conventional communications system uses a quasi-cyclic (QC: Quasi-Cyclic) code as an example of an LDPC code (refer to the following nonpatent reference 1).
First, a flow of an encoding process and a decoding process which are carried out by the conventional communications system will be explained briefly.
An LDPC encoder mounted in a communication device on a transmit side (referred to as a “transmitter” from here on) generates a parity check matrix H (which will be mentioned below in detail).
The LDPC encoder also generates, for example, a generator matrix G with K rows and N columns (K: an information length, N: a codeword length).
In this case, when the parity check matrix for LDPC is expressed as H (with M rows and N columns), the generator matrix G satisfies GHT=0 (T denotes the transposed matrix).
When receiving a message (m1, m2, . . . , mK) having the information length K, the LDPC encoder generates a codeword C from the message (m1, m2, . . . mK) by using the generator matrix G generated previously, as shown in the following equation (1). In this case, H(c1, c2, . . . , cN)T=0 is assumed.
                                                        C              =                                                (                                                            m                      1                                        ,                                          m                      2                                        ,                    …                    ⁢                                                                                  ,                                          m                      K                                                        )                                ⁢                G                                                                                        =                              (                                                      c                    1                                    ,                                      c                    2                                    ,                  …                  ⁢                                                                          ,                                      c                    N                                                  )                                                                        (        1        )            
After the LDPC encoder generates the codeword C, a modulator of the transmitter carries out digital modulation of the codeword C by using a predetermined modulation method (e.g., BPSK (Binary Phase Shift Keying), QPSK (Quadrature Phase Shift Keying), or multiple value QAM (Quadrature Amplitude Modulation)), and transmits the modulated signal x=(x1, x2, . . . , xN) to a communication device on a receive side (referred to as a “receiver” from here on).
It is assumed that in an error occurs in the modulated signal x=(x1, x2, . . . , xN) transmitted from the transmitter during transmission through the radio channel, and the signal including the error is received by the receiver.
When receiving the modulated signal y=(y1, y2, . . . , yN) including the error, the demodulator of the receiver performs digital demodulation according to the modulation method, such as BPSK, QPSK, or multiple value QAM, on the modulated signal y=(y1, y2, . . . , yN).
When receiving the demodulated result of the demodulator, the LDPC decoder of the receiver performs iterative decoding according to the “sum-product algorithm” on the demodulated result so as to decode the demodulated result into the message (m1, m2, . . . , mK) having the information length K, and then outputs the message (m1, m2, . . . , mK).
Hereafter, the parity check matrix for LDPC code will be explained concretely.
For example, in the following nonpatent reference 1, a parity check matrix HQC for QC codes as shown in FIG. 6 is proposed as a parity check matrix for LDPC code.
The parity check matrix HQC for QC code as shown in FIG. 6 is the one in which cyclic permutation matrices (p=5) each with five rows and five columns are arranged in a vertical direction (J=3) and in a horizontal direction (L=5).
Generally, a parity check matrix HQC for a (J,L)-QC code with M (=pJ) rows and N (=pL) columns can be defined as shown in the following equation (2).
      [          Equation      ⁢                          ⁢      1        ]                                                          H                              QC                i                                      =                          [                                                                                          I                      ⁡                                              (                                                  p                                                      0                            ,                            0                                                                          )                                                                                                                        I                      ⁡                                              (                                                  p                                                      0                            ,                            1                                                                          )                                                                                                  ⋯                                                                              I                      ⁡                                              (                                                  p                                                      0                            ,                                                          L                              -                              1                                                                                                      )                                                                                                                                                        I                      ⁡                                              (                                                  p                                                      1                            ,                            0                                                                          )                                                                                                                        I                      ⁡                                              (                                                  p                                                      1                            ,                            1                                                                          )                                                                                                  ⋯                                                                              I                      ⁡                                              (                                                  p                                                      0                            ,                                                          L                              -                              1                                                                                                      )                                                                                                                                  ⋮                                                        ⋮                                                        ⋱                                                        ⋮                                                                                                              I                      ⁡                                              (                                                  p                                                                                    J                              -                              1                                                        ,                            0                                                                          )                                                                                                                        I                      ⁡                                              (                                                  p                                                                                    J                              -                              1                                                        ,                            1                                                                          )                                                                                                  ⋯                                                                              I                      ⁡                                              (                                                  p                                                      0                            ,                                                          L                              -                              1                                                                                                      )                                                                                                        ]                                ⁢                                          ⁢                                                                      Example:                                ⁢                p                            =              5                        ,                                          I                ⁡                                  (                  0                  )                                            =                                                [                                                                                    1                                                                    0                                                                    0                                                                    0                                                                    0                                                                                                            0                                                                    1                                                                    0                                                                    0                                                                    0                                                                                                            0                                                                    0                                                                    1                                                                    0                                                                    0                                                                                                            0                                                                    0                                                                    0                                                                    1                                                                    0                                                                                                            0                                                                    0                                                                    0                                                                    0                                                                    1                                                                              ]                                ·                                                                          (          2          )                    where p is an odd prime number, L is the number of cyclic permutation matrices arranged in the horizontal direction (column direction) in the parity check matrix HQC, and J is the number of cyclic permutation matrices arranged in the vertical direction (row direction) in the parity check matrix HQC.
In each cyclic permutation matrix I(pj,l), at 0≦j≦J−1 and 0≦l≦L−1, matrix elements whose row number is r (0≦r≦p−1) and whose column number is (r+pj,l) mod p are “1”s, and other matrix elements are “0”s.
“A mod B” is a mathematical symbol for calculating the remainder of the division of A by B.
Because a degradation of the performance is typically caused in case in which there exist many loops having a short length when designing an LDPC code, it is necessary to increase the girth and lessen the number of loops (loop 4, loop 6, and so on) having a short length.
FIG. 7 is an explanatory drawing showing an example of the check matrix expressed in a form of a Tanner graph.
In the parity check matrix H with M rows and N columns having two elements {0, 1}, a node corresponding to each column is referred to as a bit node bn (1≦n≦N) (corresponding to ∘ in FIG. 7) and a node corresponding to each row is referred to as a check node cm (1≦m≦M) (corresponding to □ in FIG. 7).
Furthermore, when “1” is located at an intersection of a row and a column of the check matrix, a bipartite graph connecting between the bit node and the check node with a branch is referred to as a Tanner graph.
Each above-mentioned “loop” shows a closed loop starting from a specific node (corresponding to ∘ or □ of FIG. 7) and ending at the node, as shown in FIG. 7.
The above-mentioned “girth” means a minimum loop.
The length of each loop is expressed by the number of branches configuring the closed loop, and each loop is simply expressed as loop 4, loop 6, loop 8, or . . . according to the length of each loop.
The following nonpatent reference 1 shows that the girth g in the parity check matrix HQC for (J,L)-QC LDPC codes falls within a range of “4≦g≦12 (g is an even number)”.
It is easy to prevent the parity check matrix from having a girth g=4, and, in many cases, the parity check matrix has a girth satisfying g≧6.    [Nonpatent reference 1] M. Fossorier “Quasi-Cyclic Low Density Parity Check Code” ISIT2003, pp. 150, Japan, Jun. 29-Jul. 4, 2003.
Because the conventional encoder is configured as mentioned above, a parity check matrix HQC having a girth g falling within a range of “4≦g≦12 (g is a even number)” is generated, while no design method of designing a parity check matrix under the conditions that it satisfies g≧6, g≧8, g≧10, g≧12, or . . . has not been disclosed. A problem is therefore that when designing an LDPC code, it is necessary to make a search using a computer, or the like to generate a parity check matrix HQC, and it takes much time to acquire an LDPC code.
A further problem is that because the conventional encoder lacks in extensibility, and also lacks in the regularity among cyclic permutation matrices, the complexity increases at a time when the conventional encoder is implemented, and any evidence that the results of a search using a computer are optimal cannot be established.
The present invention is made in order to solve the above-mentioned problems, and it is therefore an object of the present invention to provide a check matrix generating device, a check matrix generating method, an encoder, a transmitter, a decoder, and a receiver which can easily generate a parity check matrix having good performance and regularity.